import java.util.*;

public class BTree {

	private BNode root;
	
	private static ArrayList<String> formulaList;

	public BTree(String str, boolean wholeTree) {
		if (wholeTree) {
			getFormulaList(str);
			root = treeFormula(null);
			traverse(root);
			root.isRoot = true;
		} else {
			root = new BNode(str);
			root.left = null;
			root.right = null;
			root.parent = null;
			root.isRoot = true;
		}
	}

	public BNode getRoot() {
		return root;
	}

	public void getFormulaList(String formula) {

		String[] formulaArray = formula.split("[ \t\n\f\r]|\\]|\\[|,");
		formulaList = new ArrayList<String>();

		for (String s : formulaArray) {  
			if (!s.equals("")) {
				formulaList.add(s);
			}
		}  

	}

	public BNode treeFormula(BNode parent) {

		String nextToken = formulaList.remove(0);
		
		if (nextToken.equals("and") || nextToken.equals("or") 
				|| nextToken.equals("eU") || nextToken.equals("aU")) {
			BNode nodeBinary = new BNode(nextToken);
			nodeBinary.left = treeFormula(nodeBinary);
			nodeBinary.right = treeFormula(nodeBinary);
			nodeBinary.parent = parent;
			return nodeBinary;
			
		} else if (nextToken.equals("not") 
				|| nextToken.equals("eAT") || nextToken.equals("aAT")) {
			
			BNode nodeUnary = new BNode(nextToken);
			nodeUnary.left = treeFormula(nodeUnary);
			nodeUnary.right = null;
			nodeUnary.parent = parent;
			return nodeUnary;
			
		} else {
			BNode nodeVar = new BNode(nextToken);
			nodeVar.parent = parent;
			return nodeVar;
		}

	}
	
	public void traverse(BNode root) {
		if (root != null) {
			if (root.parent != null) {
				System.out.println(root.getVal() + "  parent:  " + root.parent.getVal());
			} else {
				System.out.println("root:  " + root.getVal());
			}
		}
		if (root.left != null) {
			traverse(root.left);
		}
		if (root.right != null) {	
			traverse(root.right);
		}
	}
}